package com.ruanruan.structure.graph.dfs;

import com.ruanruan.structure.graph.AdjList;
import com.ruanruan.structure.graph.Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class SingleSourcePath {


    private final Graph G;

    private final int s;

    private final boolean[] visited;

    private final int[] pre;

    public SingleSourcePath(Graph G, int s) {
        this.G = G;
        this.s = s;

        visited = new boolean[G.V()];
        pre = new int[G.V()];
        Arrays.fill(pre, -1);
        dfs(s, s);
    }

    private void dfs(int v, int parent) {
        visited[v] = true;
        pre[v] = parent;

        for (int w : G.adj(v)) {
            if (!visited[w ]) {
                dfs(w, v);
            }
        }
    }

    public boolean isConnectedTo(int w) {
        G.validateVertex(w);
        return pre[w] != -1;
    }

    public Iterable<Integer> path(int w) {
        ArrayList<Integer> res = new ArrayList<>();
        if (!isConnectedTo(w)) {
            return res;
        }

        int cur = w;
        while (cur != s) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        SingleSourcePath path = new SingleSourcePath(new AdjList("resources/graph/g_cc.txt"), 0);
        System.out.println(path.path(6));
    }
}
